package _16_hash_table;

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author: mornd
 * @dateTime: 2023/6/19 - 23:08
 * 哈希表定义
 */
class HashTable {
    Entry[] table;
    int size;
    // 扩容因子
    final float loadFactor = 0.75f;
    // 扩容阈值
    int threshold;

    public HashTable() {
        this(16);
    }

    public HashTable(int capacity) { // capacity  必须为 2^n
        table = new Entry[capacity];
        threshold = (int) (loadFactor * table.length);
    }

    Object get(Object key) {
        return get(hash(key), key);
    }

    void put(Object key, Object value) {
        put(hash(key), key, value);
    }

    private int hash(Object key) {
        int h;
        return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    Object remove(Object key) {
        return remove(hash(key), key);
    }


    Object get(int hash, Object key) {
        int i = hash & (table.length - 1);
        Entry e = table[i];
        while (e != null) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                return e.value;
            }
            e = e.next;
        }
        return null;
    }

    /**
     * 插入或更新
     */
    void put(int hash, Object key, Object value) {
        int i = hash & table.length - 1;
        Entry e = table[i];
        Entry prev = null;
        while (e != null) {
            if (e.key == key || (key != null && key.equals(e.key))) {
                e.value = value;
                return;
            }
            prev = e;
            e = e.next;
        }
        Entry newE = new Entry(hash, key, value);
        if (prev == null) {
            table[i] = newE;
        } else {
            prev.next = newE;
        }
        if (++size > threshold) {
            resize();
        }
    }

    /**
     * 扩容
     */
    private void resize() {
        // 扩容2倍
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry e = table[i];
            if (e != null) {
                // 拆分成两个新链表，再移动到新数组
                Entry a = null, b = null;
                // 存储两个新链表的头元素
                Entry aHead = null, bHead = null;
                /*
                    hash & table.length == 0 的一组
                    hash & table.length != 0 的一组
                 */
                while (e != null) {
                    if ((e.hash & table.length) == 0) {
                        if (a != null) {
                            // 更换链表间的指针，a一组，b一组
                            a.next = e;
                        } else {
                            // 记录链表头
                            aHead = e;
                        }
                        a = e;
                    } else {
                        if (b != null) {
                            b.next = e;
                        } else {
                            bHead = e;
                        }
                        b = e;
                    }
                    e = e.next;
                }

                if (a != null) {
                    // 去除多余的尾部节点
                    a.next = null;
                    // a插入新数组的下标不变
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    // b插入 当前下标+旧链表长度 的位置
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length);
    }

    Object remove(int hash, Object key) {
        int i = hash & table.length - 1;
        Entry e = table[i];
        Entry prev = null, curr = null;
        while (e != null) {
            if (e.key == key || (key != null && key.equals(e.key))) {
                curr = e;
                break;
            }
            prev = e;
            e = e.next;
        }

        if (curr == null) {
            return null;
        }
        if (prev == null) {
            table[i] = curr.next;
        } else {
            prev.next = curr.next;
        }
        size--;
        return curr.value;
    }

    static class Entry {
        int hash;
        Object key;
        Object value;
        Entry next;

        public Entry(Object key, Object value) {
            this.value = value;
            this.key = key;
        }

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.value = value;
            this.key = key;
        }

        @Override
        public String toString() {
            return "(" + key + ", " + value + ")";
        }
    }

    public int size() {
        return size;
    }

    public void printTableStructure() {
        for (int i = 0; i < table.length; i++) {
            System.out.print("Bucket " + i + ": ");
            Entry entry = table[i];
            while (entry != null) {
                System.out.print(entry + " -> ");
                entry = entry.next;
            }
            System.out.println();
        }
        System.out.println();
    }

    public Map classify() {
        int[] arr = new int[table.length];
        for (int i = 0; i < table.length; i++) {
            Entry e = table[i];
            int c  = 0;
            while (e != null) {
                c++;
                e = e.next;
            }
            arr[i] = c;
        }
        return Arrays.stream(arr).boxed()
                .collect(Collectors.groupingBy(e -> e, Collectors.counting()));
    }
}
